Un {\em k-mot}, ou {\em k-mer} est un extrait de séquence de k nucléotide(s). Dans le projet il est représenté par un {\em pattern} construit avec les caractères '\#' et '\_', le nombre de dièse correspond à la valeur de k. 

\paragraph{Principe du comptage}
~\\

Tout d'abord, on fait l'hypothèse que la fréquence en K-mot de chaque taxon, peut représenter une signature pertinente.

Il existe plusieurs façons d'établir la signature d'un taxon~\cite{autre}, comme par exemple utiliser simplement les séquences du génome associé et de faire une comparaison naïve.\\

Étant donné le contexte du projet, la méthode utilisée est le comptage de {\em k-mots} (ou k-mers) ~\cite{kmer}. Cela consiste à compter un motif de longueur k dans un mot construit ici avec l'alphabet de l'ADN $\Sigma = \{A,C,G,T\}$. Ces motifs sont représentés par un pattern constitué du caractère '\#'. Par exemple pour un 2-mers le pattern correspondant est \#\# et c'est tous les mots de taille deux qu'on peut former 
avec l'alphabet $\Sigma$ soit $\{AA,AC,AG,AT,CA,CC,CG,CT,GA,GC,GG,GT,TA,TC,TG,TT\}$, que l'on va dénombrer au long de la séquence.
\\

Par exemple pour la séquence: $S = $ $ACTACGTACCGATAT$ et le pattern $p_1 = $\#\# avec $k_1 = 2$;

\begin{figure}[H]
\begin{center}
\begin{tabular}{|*{16}{c|}}
  \hline
  AA & AC & AG & AT & CA & CC & CG & CT & GA & GC & GG & GT & TA & TC & TG & TT \\
  \hline
  0 & 3 & 0 & 2 & 0 & 1 & 1 & 1 & 1 & 0 & 1 & 1 & 3 & 0 & 0 & 0 \\
  \hline
\end{tabular}
\caption[Exemple de comptage 2-mers avec le pattern \#\#]{\label{2mer}Exemple de comptage 2-mers avec le pattern \#\#. Ici on a compté aucun AA, 3 AC,...et 0 TT dans la séquence ACTACGTACCGATAT.}
\end{center}
\end{figure}

On se donne aussi la possibilité de compter des patterns espacés. Par opposition aux patterns continus précédents, ceux-ci sont représentés avec les lettres '\#' et '\_'. Le principe reste le même 
sauf qu'ici 
on ne prend pas en compte les '\_' dans le pattern pour le comptage. Par exemple pour le k-mer décrit par le pattern \#\_\# on va compter tous les mots de taille deux (nombre de '\#') soit $\{AA,AC,...,TT\}$, mais cette fois
ci ces mots seront compté dans des fenêtres de taille trois (taille du pattern) et le 2-mer correspondant sera formé par les lettres lues aux positions marquées par les dièses. Par exemple dans le mot $ACGT$ avec le pattern \#\_\# on 
va comptabiliser les 2-mers AG 
\begin{tabular}{*{4}{c}}
  A & C & G & T  \\
  \# & \_ & \# &  \\
\end{tabular} et $CT$ \begin{tabular}{*{4}{c}}
  A & C & G & T  \\
   & \# & \_ & \#  \\
\end{tabular}
~\\
\newpage
Par exemple pour la séquence $S$ et le pattern $p_2 =$ \#\_\# avec $k_2$ = 2.

\begin{figure}[H]
\begin{center}
\begin{tabular}{|*{16}{c|}}
  \hline
  AA & AC & AG & AT & CA & CC & CG & CT & GA & GC & GG & GT & TA & TC & TG & TT \\
  \hline
  1 & 1 & 1 & 1 & 2 & 0 & 1 & 1 & 1 & 0 & 0 & 1 & 0 & 2 & 0 & 1 \\
  \hline
\end{tabular}
\caption[Comptage 2-mers avec le pattern \#\_\#]{\label{2mer-espace}Comptage 2-mers avec le pattern \#\_\#. Ici on a comptabilisé 1 AA, 1 AC,..et 1 TT dans la séquence ACTACGTACCGATAT }
\end{center}
\end{figure}
~\\

On peut voir ce tableau comme un vecteur dans un espace à $4^k$ dimensions, où $k$ représente la taille du k-mer. La première composante représente le nombre de k-mer AAA..A (k fois A), la seconde correspond au k-mer $AAA...AC$ (k-1 fois A et 1 fois C), et la dernière composante serait le dernier k-mer $TTT...T$ (k fois T). Il est possible de considérer différents patterns pour la signature d'un taxon, dans ce cas le vecteur représentant la signature sachant le comptage
avec ces différents k-mers sera la concaténation de chaque vecteurs résultant des comptages faits pour chaque k-mer.
\\

Pour la séquence $S$ et les patterns \textcolor{red}{$p_1$} et \textcolor{blue}{$p_2$} alors le vecteur résultant est 
\begin{figure}[H]
\begin{center}
$\overrightarrow{V} = \{\textcolor{red}{0,3 ,0 ,2 ,0 ,1 , 1 , 1 , 1 , 0 , 1 , 1 , 3 , 0 , 0 , 0 ,}\textcolor{blue}{ 1 , 1 , 1 , 1 , 2 , 0 , 1 , 1 , 1 , 0 , 0 , 1 , 0 , 2 , 0 , 1}\} $
\end{center}
\end{figure}
~\\

Où les $4^{k_1 = 2}$ premières fréquences correspondent au comptage de 2-mers du pattern $p_1$ (figure \ref{2mer}) et les $4^{k_2 = 2}$ dernières fréquences au comptage des 2-mers du pattern $p_2$ (figure \ref{2mer-espace}).
\\

Au final pour un taxon donné $t$ , si on effectue le comptage par rapport à $n$ de ses séquences avec $d$ patterns $p_1,...,p_d$ et ayant respectivement $k_1,...,k_d$ dièses (soit la taille respective des mers), on aura alors $n$ points dans l'espace à $\sum\limits_{i=1}^d k^d$ dimensions. On aura ainsi le nuage de points dans cet espace caractérisant $t$.

\paragraph{Algorithme de comptage}
~\\

\input{./comptageAlgo.tex}
